1. Field of the Invention
This invention relates to software programs that produce topological representations of networks from geometric representations.
2. Background Information
In many civil engineering applications and in other engineering fields, software programs are employed to model and graphically represent a network including a set of links and nodes. Such resultant representations may be topological representations generated from geometric representations stored in a global information system (GIS), or a computer aided design system (CAD). These geometric systems provide a spatial description of a network which can be used to construct a topological representation of a network (such as a water distribution system that is a lattice of pipes and junctions, which are the links and nodes in that particular application). Software programs that generate topological representations use the spatial proximity data inherent to the underlying geometric representation to construct a topological representation of the network (which can then be used to model system behavior).
There can, however, be inaccuracies in the resulting network representation due to some inherent difficulties in topology, particularly in areas where there is a close proximity between two (or more) data structures. Such data structures are sometimes referred to as “nearest neighbors”. The user of the geometric representation software program, for example, can graphically draw nodes or links in close proximity, incorrectly. Geometrically, for example, a T intersection may visually appear to exist in the representation of a water distribution network; however, if not drawn correctly the pipes at the T-intersection would not be topologically connected at a junction. Inaccuracies in the geometric representation are generally not overly problematic, because the visual representation appears correct. But when these geometric inaccuracies are propagated to the topological representation, hard to detect problems arise because the model will not accurately reflect the behavior of the “real” system.
As noted, software programs are available that generate network models and other representations. Some of these programs include features for identifying some aspects of topological inaccuracies. However, they can be based on iterative sequential searching, which can be quite slow. In addition, such programs may require the user to view hundreds of essentially redundant potential candidates, which can be laborious and time consuming, and which can lead to human errors. In the case of the “pipe split candidate node” search, for example, it would not be feasible to perform a generic spatial query for nodes in close proximity to pipes, because every node in the system is in close proximity to a pipe. There remains a need, therefore, for a method of detecting nearest neighbor topology problems, which quickly locates potential candidates and provides a manageably short list to a user for review. There remains a further need for such a software program that provides the user an opportunity to navigate to the potentially problematic location in the network representation and to take corrective action that can be implemented quickly.